/***********************************************************************

	This file is part of KEEL-software, the Data Mining tool for regression, 
	classification, clustering, pattern mining and so on.

	Copyright (C) 2004-2010
	
	F. Herrera (herrera@decsai.ugr.es)
    L. Sánchez (luciano@uniovi.es)
    J. Alcalá-Fdez (jalcala@decsai.ugr.es)
    S. García (sglopez@ujaen.es)
    A. Fernández (alberto.fernandez@ujaen.es)
    J. Luengo (julianlm@decsai.ugr.es)

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see http://www.gnu.org/licenses/
  
**********************************************************************/

/*
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

package keel.Algorithms.SVM.SMO.supportVector;

import keel.Algorithms.SVM.SMO.core.Option;
import keel.Algorithms.SVM.SMO.core.Utils;
import keel.Algorithms.SVM.SMO.core.Instance;
import keel.Algorithms.SVM.SMO.core.Instances;
import keel.Dataset.Attributes;

import java.util.Enumeration;
import java.util.Vector;

/**
 * Base class for RBFKernel and PolyKernel that implements a simple LRU.
 * (least-recently-used) cache if the cache size is set to a value > 0.
 * Otherwise it uses a full cache.
 * 
 * @author Eibe Frank (eibe@cs.waikato.ac.nz)
 * @author Shane Legg (shane@intelligenesis.net) (sparse vector code)
 * @author Stuart Inglis (stuart@reeltwo.com) (sparse vector code)
 * @author J. Lindgren (jtlindgr{at}cs.helsinki.fi) (RBF kernel)
 * @author Steven Hugg (hugg@fasterlight.com) (refactored, LRU cache)
 * @author Bernhard Pfahringer (bernhard@cs.waikato.ac.nz) (full cache)
 * @version $Revision: 1.1 $
 */
public abstract class CachedKernel 
extends Kernel {

	/** for serialization */
	private static final long serialVersionUID = 702810182699015136L;

	/** Counts the number of kernel evaluations. */
	protected int m_kernelEvals;

	/** Counts the number of kernel cache hits. */
	protected int m_cacheHits;

	/** The size of the cache (a prime number) */
	protected int m_cacheSize = 250007;

	/** Kernel cache */
	protected double[] m_storage;
        /** Kernel cache (keys)*/
	protected long[] m_keys;

	/** The kernel matrix if full cache is used (i.e. size is set to 0) */
	protected double[][] m_kernelMatrix;

	/** The number of instance in the dataset */
	protected int m_numInsts;

	/** number of cache slots in an entry */
	protected int m_cacheSlots = 4;

	/**
	 * default constructor - does nothing.
	 */
	public CachedKernel() {
		super();
	}

	/**
	 * Initializes the kernel cache. The actual size of the cache in bytes is
	 * (64 * cacheSize).
	 * 
	 * @param data	the data to use
	 * @param cacheSize	the cache size
	 * @throws Exception	if something goes wrong
	 */
	protected CachedKernel(Instances data, int cacheSize) throws Exception {
		super();

		setCacheSize(cacheSize);

		buildKernel(data);
	}

	/**
	 * Returns an enumeration describing the available options.
	 *
	 * @return 		an enumeration of all the available options.
	 */
	public Enumeration listOptions() {
		Vector		result;
		Enumeration		en;

		result = new Vector();

		en = super.listOptions();
		while (en.hasMoreElements())
			result.addElement(en.nextElement());

		result.addElement(new Option(
				"\tThe size of the cache (a prime number), 0 for full cache and \n"
				+ "\t-1 to turn it off.\n"
				+ "\t(default: 250007)",
				"C", 1, "-C <num>"));

		return result.elements();
	}

	/**
	 * Parses a given list of options. <p/>
	 * 
	 * @param options 	the list of options as an array of strings
	 * @throws Exception 	if an option is not supported
	 */
	public void setOptions(String[] options) throws Exception {
		String	tmpStr;

		tmpStr = Utils.getOption('C', options);
		if (tmpStr.length() != 0)
			setCacheSize(Integer.parseInt(tmpStr));
		else
			setCacheSize(250007);

		super.setOptions(options);
	}

	/**
	 * Gets the current settings of the Kernel.
	 *
	 * @return an array of strings suitable for passing to setOptions
	 */
	public String[] getOptions() {
		int       i;
		Vector    result;
		String[]  options;

		result = new Vector();
		options = super.getOptions();
		for (i = 0; i < options.length; i++)
			result.add(options[i]);

		result.add("-C");
		result.add("" + getCacheSize());

		return (String[]) result.toArray(new String[result.size()]);	  
	}

	/**
	 * This method is overridden in subclasses to implement specific kernels.
	 * 
	 * @param id1   	the index of instance 1
	 * @param id2		the index of instance 2
	 * @param inst1	the instance 1 object
	 * @return 		the dot product
	 * @throws Exception 	if something goes wrong
	 */
	protected abstract double evaluate(int id1, int id2, Instance inst1)
	throws Exception;

	/**
	 * Implements the abstract function of Kernel using the cache. This method
	 * uses the evaluate() method to do the actual dot product.
	 *
	 * @param id1 	the index of the first instance in the dataset
	 * @param id2 	the index of the second instance in the dataset
	 * @param inst1 	the instance corresponding to id1 (used if id1 == -1)
	 * @return 		the result of the kernel function
	 * @throws Exception 	if something goes wrong
	 */
	public double eval(int id1, int id2, Instance inst1) throws Exception {

		double result = 0;
		long key = -1;
		int location = -1;

		// we can only cache if we know the indexes and caching is not 
		// disbled (m_cacheSize == -1)
		if ( (id1 >= 0) && (m_cacheSize != -1) ) {

			// Use full cache?
			if (m_cacheSize == 0) {
				if (m_kernelMatrix == null) {
					m_kernelMatrix = new double[m_data.numInstances()][];
					for(int i = 0; i < m_data.numInstances(); i++) {
						m_kernelMatrix[i] = new double[i + 1];
						for(int j = 0; j <= i; j++) {
							m_kernelEvals++;
							m_kernelMatrix[i][j] = evaluate(i, j, m_data.instance(i));
						}
					}
				} 
				m_cacheHits++;
				result = (id1 > id2) ? m_kernelMatrix[id1][id2] : m_kernelMatrix[id2][id1];
				return result;
			}

			// Use LRU cache
			if (id1 > id2) {
				key = (id1 + ((long) id2 * m_numInsts));
			} else {
				key = (id2 + ((long) id1 * m_numInsts));
			}
			location = (int) (key % m_cacheSize) * m_cacheSlots;
			int loc = location;
			for (int i = 0; i < m_cacheSlots; i++) {
				long thiskey = m_keys[loc];
				if (thiskey == 0)
					break; // empty slot, so break out of loop early
				if (thiskey == (key + 1)) {
					m_cacheHits++;
					// move entry to front of cache (LRU) by swapping
					// only if it's not already at the front of cache
					if (i > 0) {
						double tmps = m_storage[loc];
						m_storage[loc] = m_storage[location];
						m_keys[loc] = m_keys[location];
						m_storage[location] = tmps;
						m_keys[location] = thiskey;
						return tmps;
					} else
						return m_storage[loc];
				}
				loc++;
			}
		}

		result = evaluate(id1, id2, inst1);

		m_kernelEvals++;

		// store result in cache
		if ( (key != -1) && (m_cacheSize != -1) ) {
			// move all cache slots forward one array index
			// to make room for the new entry
			System.arraycopy(m_keys, location, m_keys, location + 1,
					m_cacheSlots - 1);
			System.arraycopy(m_storage, location, m_storage, location + 1,
					m_cacheSlots - 1);
			m_storage[location] = result;
			m_keys[location] = (key + 1);
		}
		return result;
	}

	/**
	 * Returns the number of time Eval has been called.
	 * 
	 * @return 		the number of kernel evaluation.
	 */
	public int numEvals() {
		return m_kernelEvals;
	}

	/**
	 * Returns the number of cache hits on dot products.
	 * 
	 * @return 		the number of cache hits.
	 */
	public int numCacheHits() {
		return m_cacheHits;
	}

	/**
	 * Frees the cache used by the kernel.
	 */
	public void clean() {
		m_storage = null;
		m_keys = null;
		m_kernelMatrix = null;
	}

	/**
	 * Calculates a dot product between two instances
	 * 
	 * @param inst1	the first instance
	 * @param inst2	the second instance
	 * @return 		the dot product of the two instances.
	 * @throws Exception	if an error occurs
	 */
	protected final double dotProd(Instance inst1, Instance inst2)
	throws Exception {

		double result = 0;

		// we can do a fast dot product
		int n1 = inst1.numValues();
	    int n2 = inst2.numValues();
		int classIndex = m_data.classIndex();
		for (int p1 = 0, p2 = 0; p1 < n1 && p2 < n2;) {
			int ind1 = p1;
			int ind2 = p2;
			if (ind1 == ind2) {
				if (ind1 != classIndex) {
					result += inst1.valueSparse(p1) * inst2.valueSparse(p2);
				}
				p1++;
				p2++;
			} else if (ind1 > ind2) {
				p2++;
			} else {
				p1++;
			}
		}
		return (result);
	}

	/**
	 * Sets the size of the cache to use (a prime number)
	 * 
	 * @param value	the size of the cache
	 */
	public void setCacheSize(int value) {
		if (value >= -1) {
			m_cacheSize = value;
			clean();
		}
		else {
			System.out.println(
					"Cache size cannot be smaller than -1 (provided: " + value + ")!");
		}
	}

	/**
	 * Gets the size of the cache
	 * 
	 * @return 		the cache size
	 */
	public int getCacheSize() {
		return m_cacheSize;
	}

	/**
	 * Returns the tip text for this property
	 * 
	 * @return 		tip text for this property suitable for
	 * 			displaying in the explorer/experimenter gui
	 */
	public String cacheSizeTipText() {
		return "The size of the cache (a prime number), 0 for full cache and -1 to turn it off.";
	}

	/**
	 * initializes variables etc.
	 * 
	 * @param data	the data to use
	 */
	protected void initVars(Instances data) {
		super.initVars(data);

		m_kernelEvals = 0;
		m_cacheHits   = 0;
		m_numInsts    = m_data.numInstances();

		if (getCacheSize() > 0) {
			// Use LRU cache
			m_storage = new double[m_cacheSize * m_cacheSlots];
			m_keys    = new long[m_cacheSize * m_cacheSlots];
		} 
		else {
			m_storage      = null;
			m_keys         = null;
			m_kernelMatrix = null;
		}
	}

	/**
	 * builds the kernel with the given data. Initializes the kernel cache. 
	 * The actual size of the cache in bytes is (64 * cacheSize).
	 * 
	 * @param data	the data to base the kernel on
	 * @throws Exception	if something goes wrong
	 */
	public void buildKernel(Instances data) throws Exception {
		// does kernel handle the data?
//		if (!getChecksTurnedOff())
//			getCapabilities().testWithFail(data);

		initVars(data);
	}
}

